Batch 2 - Class 292 - Game of Bridg-it

• (536Henry: Problem 297) Here is a square plot of land with four houses, four trees, a well (W) in the center, and hedges planted across the four gateways (G). Can you divide the ground so that each householder shall have an equal portion of land, one tree, one gateway, an equal length of hedge, and free access to the well without trespass?

• Answer: 

  

• Play the game of Bridg-It to understand the game mechanics
• Can this game end in a draw? Why or why not?
• An end-to-end path can not be blocked except by another end to end path, hence the game can not end in a draw
• Discuss strategies of winning in Bridg-it
• Proof
• Define notion of spanning tree - covers all vertices, and there is exactly one path between any two vertices. If we remove an edge from a tree, the graph breaks into two unconnected sub-trees
• Suppose we construct two spanning trees on a connected graph, so that there is no common edge. Think of this as two road networks for example (Illustrate to students). Think of one as primary tree and the second as secondary. What can we do if one of the edges in primary network is disconnected. What do we have to do to reconnect those vertices using edges of the second tree? Specifically, how many and which edge do we have to add?
• These are called edge-disjoint spanning trees
• How can we apply this to Bridg-it?
• What if we identify two "edge-disjointed spanning trees" in Bridg-it potential connections?
• What can break an edge in the primary tree?
• An opponent's move!
• Now whenever player 2 plays, they are effectively disconnecting player 1's primary tree. Player 1 just has to reconnect it using a suitable edge from secondary tree (or vice-versa). Note that since there is no common edge between primary tree and secondary, player 2 can't remove both simultaneously
• Player 1's edge creates a shared edge between both trees and can not be broken by second player. Think of player 2's zeroth move as removing the big arc from first tree.
• Illustrate the method by playing successive turns and creating and erasing edges. Explain why the vertices at extreme ends have been collapsed into a single vertex.

• So player 1 always has a winning strategy, and unlike Hex, we actually know the winning strategy here! Just keep connecting the trees by borrowing edges from the second tree.
• Let students play another round to see if they have understood.

• (Geoffrey - 64) As soon as the news of bank robbery came in, a police car was sent to High Street bridge. The robbers had made their escape in a car, and the bridge was the only point of escape north of town. The police car took strategic position at point A on the map. Three patrols were assigned to patrol A-B, A-D and A-C, each going back and forth the blocks 200mx100m in size, at uniform speed of 10km/hr. All of them started from point A at 4am. On the first occasion thereafter when the three met at the car together, a radio message advised them that the robbers had escaped from south side of town. What time did the message arrive?

• Answer: Each patrol must have run 72 lengths of blocks, i.e. 14400 metres when they first get together. At 10km/hr, this means about 1:26 hrs, so time must be 5:26 am